package com.lcz.suanfa;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

/**
 * <pre>
 * <img width="128" height="110" src="https://tse3-mm.cn.bing.net/th/id/OIP-C.en-w_oH-yn2UsSRfWnOsGAHaGY?w=198&h=180&c=7&r=0&o=5&dpr=1.25&pid=1.7" alt="马刺">
 * 作者:     <a href="https://github.com/liuchuanzheng">刘传政</a>
 * 创建时间:  9:46 2022/2/16 0016
 * QQ:      1052374416
 * 电话:     18501231486
 * 描述:
 * </pre>
 */
public class Suanfa_数组 {
    @Test
    public void test_删除排序数组中的重复项() {
        int[] nums = {1, 1, 2};
        int count = removeDuplicates(nums);
        assert count == 2;
    }

    //https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2gy9m/
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int index = 0;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[index]) {
                index = index + 1;
                count++;
                nums[index] = nums[i];
            }

        }
        return count;
    }

    @Test
    public void test_买卖股票的最佳时机() {
        int[] nums = {1, 2, 3, 4, 5};
        int count = maxProfit(nums);
        System.out.println(count);
        assert count == 4;
    }

    //https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2zsx1/
    public int maxProfit(int[] prices) {
        int lirun = 0;
        int myPrice = -1;
        for (int i = 0; i < prices.length - 1; i++) {
            int today = prices[i];
            int nextDay = prices[i + 1];
            if (nextDay > today) {
                //买
                if (myPrice != -1) {
                    //卖
                    lirun += (today - myPrice);
                    myPrice = -1;
                }
                myPrice = today;
            } else if (nextDay == today) {
            } else {
                if (myPrice != -1) {
                    //卖
                    lirun += (today - myPrice);
                    myPrice = -1;
                }
            }

        }
        int lastDay = prices[prices.length - 1];
        if (myPrice != -1) {
            //卖
            if (lastDay > myPrice) {
                lirun += (lastDay - myPrice);
                myPrice = -1;
            }
        }
        return lirun;
    }

    @Test
    public void test_旋转数组() {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        rotate(nums, 3);
        for (int num : nums) {
            System.out.println(num);
        }
    }

    //https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2skh7/
    public void rotate(int[] nums, int k) {
        if (k % nums.length == 0) {
            return;
        }
        if (nums.length == 1) {
            return;
        }


        int n = nums.length;
        int[] newArr = new int[n];
        for (int i = 0; i < n; ++i) {
            newArr[(i + k) % n] = nums[i];
        }
        System.arraycopy(newArr, 0, nums, 0, n);

    }

    @Test
    public void test_存在重复元素() {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        boolean b = containsDuplicate(nums);
        assert b == false;
    }

    //https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x248f5/
    public boolean containsDuplicate(int[] nums) {
        boolean result = false;
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (set.contains(num)) {
                result = true;
                break;
            } else {
                set.add(num);
            }
        }
        return result;
    }

    @Test
    public void test_只出现一次的数字() {
        int[] nums = {4, 1, 2, 1, 2};

    }

    //https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x21ib6/
    public int singleNumber(int[] nums) {
        int result = nums[0];
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                set.remove(nums[i]);
            } else {
                set.add(nums[i]);
            }
        }
        for (Integer integer : set) {
            result = integer;
        }
        return result;
    }

    public int singleNumber2(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;

    }

    @Test
    public void test_两个数组的交集() {
        int[] nums = {4, 1, 2, 1, 2};

    }

    //https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2y0c2/
    public int[] intersect(int[] nums1, int[] nums2) {
        int[] max;
        int[] min;
        if (nums1.length >= nums2.length) {
            max = nums1;
            min = nums2;
        } else {
            max = nums2;
            min = nums1;
        }
        int[] result = new int[max.length];

        for (int i = 0; i < max.length; i++) {
            result[i] = -1;
            for (int j = 0; j < min.length; j++) {
                if (max[i] == min[j]) {
                    result[i] = max[i];
                    min[j] = -1;
                    break;
                }

            }
        }
        ArrayList<Integer> list = new ArrayList<>();
        for (int i : result) {
            if (i != -1) {
                list.add(i);
            }
        }
        result = list.stream().mapToInt(Integer::valueOf).toArray();
        return result;
    }

    /**
     * 加一
     * 给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
     * <p>
     * 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
     * <p>
     * 你可以假设除了整数 0 之外，这个整数不会以零开头。
     * <p>
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2cv1c/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * @param digits
     * @return
     */
    public int[] plusOne(int[] digits) {
        return plusOne(digits, digits.length - 1);
    }

    public int[] plusOne(int[] digits, int index) {
        if (index == 0) {
            int i0 = digits[0];
            i0++;
            if (i0 < 10) {
                digits[0] = i0 % 10;
                return digits;
            } else {
                digits[0] = i0 % 10;
                int[] arr = new int[digits.length + 1];
                arr[0] = 1;
                for (int i = 0; i < digits.length; i++) {
                    arr[i + 1] = digits[i];
                }
                return arr;
            }
        }

        int i = digits[index];
        i++;
        int shang = i / 10;
        int yu = i % 10;
        digits[index] = yu;
        if (shang == 1) {
            index--;
            return plusOne(digits, index);
        } else {
            return digits;
        }
    }

    //给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
    //
    //请注意 ，必须在不复制数组的情况下原地对数组进行操作。
    public void moveZeroes(int[] nums) {
        int indexNot0 = -1;
        int indexMove = -1;
        int temp = 0;
        for (int i = 0; i < nums.length; i++) {
            indexMove = i;
            if (nums[i] != 0) {
                indexNot0++;
                if (indexNot0 != indexMove) {
                    temp = nums[indexNot0];
                    nums[indexNot0] = nums[i];
                    nums[i] = temp;
                }

            }
        }
    }

    @Test
    public void test_两数之和() {
        int[] nums = {0, 4, 3, 0};
        int[] ints = twoSum(nums, 0);
        for (int anInt : ints) {
            System.out.println(anInt);
        }

    }

    /**
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
     * <p>
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
     * <p>
     * 你可以按任意顺序返回答案。
     * <p>
     *  
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [2,7,11,15], target = 9
     * 输出：[0,1]
     * 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
     * 示例 2：
     * <p>
     * 输入：nums = [3,2,4], target = 6
     * 输出：[1,2]
     * 示例 3：
     * <p>
     * 输入：nums = [3,3], target = 6
     * 输出：[0,1]
     * <p>
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2jrse/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        int[] resultIndexArray = new int[2];
        int first = 0;
        for (int i = 0; i < nums.length; i++) {

            if (i == nums.length - 1) {
                break;
            }
            first = nums[i];
            resultIndexArray[0] = i;
            for (int i1 = (i + 1); i1 < nums.length; i1++) {
                if (nums[i1] + first == target) {
                    resultIndexArray[1] = i1;
                    return resultIndexArray;
                }
            }
        }
        return resultIndexArray;
    }

    @Test
    public void test_有效的数独() {
        char[][] board = {{'.', '.', '4', '.', '.', '.', '6', '3', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'5', '.', '.', '.', '.', '.', '.', '9', '.'},
                {'.', '.', '.', '5', '6', '.', '.', '.', '.'},
                {'4', '.', '3', '.', '.', '.', '.', '.', '1'},
                {'.', '.', '.', '7', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '5', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'}};
        boolean validSudoku = isValidSudoku(board);
        System.out.println(validSudoku);

    }

    //[[".",".","4",".",".",".","6","3","."],
    // [".",".",".",".",".",".",".",".","."],
    // ["5",".",".",".",".",".",".","9","."],
    // [".",".",".","5","6",".",".",".","."],
    // ["4",".","3",".",".",".",".",".","1"],
    // [".",".",".","7",".",".",".",".","."],
    // [".",".",".","5",".",".",".",".","."],
    // [".",".",".",".",".",".",".",".","."],
    // [".",".",".",".",".",".",".",".","."]]
    //https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2f9gg/
    public boolean isValidSudoku(char[][] board) {
        boolean isValid = true;
        isValid = checkHang(board);
        if (isValid) {
            isValid = checkLie(board);
            if (isValid) {
                isValid = checkSquare(board, 0);
            }
        }

        return isValid;
    }

    public boolean checkHang(char[][] board) {
        boolean isValid = true;
        HashSet<Character> set = new HashSet<Character>();
        for (int i = 0; i < board.length; i++) {
            set.clear();
            char[] hang = board[i];
            for (char c : hang) {
                if (c != '.') {
                    if (set.contains(c)) {
                        return false;
                    } else {
                        set.add(c);
                    }
                }
            }
        }
        return isValid;
    }

    public boolean checkLie(char[][] board) {
        boolean isValid = true;
        HashSet<Character> set = new HashSet<Character>();
        for (int i = 0; i < board[0].length; i++) {
            //列
            set.clear();
            for (int j = 0; j < board.length; j++) {
                //行
                char lie = board[j][i];
                if (lie != '.') {
                    if (set.contains(lie)) {
                        return false;
                    } else {
                        set.add(lie);
                    }
                }
            }

        }
        return isValid;
    }

    //检查每个大方格里边是否符合要求
    public boolean checkSquare(char[][] board, int squareIndex) {
        int shang = squareIndex / 3;
        int yu = squareIndex % 3;
        int hangStart = 3 * shang;
        int hangEnd = hangStart + 2;
        int lieStart = 3 * yu;
        int lieEnd = lieStart + 2;

        boolean isValid = true;
        HashSet<Character> set = new HashSet<Character>();
        for (int i = hangStart; i <= hangEnd; i++) {
            for (int j = lieStart; j <= lieEnd; j++) {

                char c = board[i][j];
                if (c != '.') {
                    if (set.contains(c)) {
                        isValid = false;
                        return isValid;
                    } else {
                        set.add(c);
                    }
                }
            }

        }
        squareIndex++;
        if (squareIndex <= 8) {
            isValid = checkSquare(board, squareIndex);
        }
        return isValid;
    }

    @Test
    public void test_旋转图像() {
        int[][] board = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        旋转图像(board);
        for (int[] ints : board) {
            System.out.println(Arrays.toString(ints));
        }


    }

    //https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnhhkv/
    public void 旋转图像(int[][] matrix) {

        for (int bianchang = matrix.length; bianchang > 1; bianchang = bianchang - 2) {
            旋转图像的一圈(matrix, bianchang);
        }


    }

    public void 旋转图像的一圈(int[][] matrix, int bianchang) {
        int totalLength = matrix.length;
        int length = bianchang * bianchang - (bianchang - 2) * (bianchang - 2);
        int[] numsShang = new int[bianchang - 1];
        int[] numsYou = new int[bianchang - 1];
        int[] numsXia = new int[bianchang - 1];
        int[] numsZuo = new int[bianchang - 1];
        int shangIndex = 0;
        int YouIndex = 0;
        int XiaIndex = 0;
        int ZuoIndex = 0;
        int hangStartIndex = (totalLength - bianchang) / 2;
        int hangEndIndex = hangStartIndex + bianchang - 1;
        int lieStartIndex = (totalLength - bianchang) / 2;
        int lieEndIndex = lieStartIndex + bianchang - 1;

        int hangIndex = hangStartIndex;
        int lieIndex = lieStartIndex;
        for (int i = 0; i < length; i++) {
            if (hangIndex == hangStartIndex && lieIndex != lieEndIndex) {
                //上边除去最后一个
                numsShang[shangIndex] = matrix[hangIndex][lieIndex];
                shangIndex++;
                lieIndex++;
            } else if (lieIndex == lieEndIndex && hangIndex != hangEndIndex) {
                //右边除去最后一个
                numsYou[YouIndex] = matrix[hangIndex][lieIndex];
                YouIndex++;
                hangIndex++;
            } else if (hangIndex == hangEndIndex && lieIndex != lieStartIndex) {
                //下边除去最后一个
                numsXia[XiaIndex] = matrix[hangIndex][lieIndex];
                XiaIndex++;
                lieIndex--;
            } else if (lieIndex == lieStartIndex && hangIndex != hangStartIndex) {
                //左边除去最后一个
                numsZuo[ZuoIndex] = matrix[hangIndex][lieIndex];
                ZuoIndex++;
                hangIndex--;
            }

        }
        System.out.println("边长" + bianchang);
        System.out.println(Arrays.toString(numsShang));
        System.out.println(Arrays.toString(numsYou));
        System.out.println(Arrays.toString(numsXia));
        System.out.println(Arrays.toString(numsZuo));
        shangIndex = 0;
        YouIndex = 0;
        XiaIndex = 0;
        ZuoIndex = 0;
        for (int i = 0; i < length; i++) {
            if (hangIndex == hangStartIndex && lieIndex != lieEndIndex) {
                //上边除去最后一个
                matrix[hangIndex][lieIndex] = numsZuo[shangIndex];
                shangIndex++;
                lieIndex++;
            } else if (lieIndex == lieEndIndex && hangIndex != hangEndIndex) {
                //右边除去最后一个
                matrix[hangIndex][lieIndex] = numsShang[YouIndex];
                YouIndex++;
                hangIndex++;
            } else if (hangIndex == hangEndIndex && lieIndex != lieStartIndex) {
                //下边除去最后一个
                matrix[hangIndex][lieIndex] = numsYou[XiaIndex];
                XiaIndex++;
                lieIndex--;
            } else if (lieIndex == lieStartIndex && hangIndex != hangStartIndex) {
                //左边除去最后一个
                matrix[hangIndex][lieIndex] = numsXia[ZuoIndex];
                ZuoIndex++;
                hangIndex--;
            }

        }

    }

}
